package main
/**
请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
 */
type ListNode struct {
	Val  int
	Next *ListNode
}
//慢 递归添加数组
func isPalindrome2(head *ListNode) bool {
	nums := []int{}
	var getList func(head *ListNode,nums []int) []int
	getList = func(head *ListNode,nums []int) []int {
		nums = append(nums, head.Val)
		if head==nil || head.Next == nil {
			return nums
		}
		return getList(head.Next,nums)
	}
	nums = getList(head,nums)
	start :=0
	end:= len(nums)-1
	for start<end {
		if nums[start] != nums[end] {
			return false
		}
		start++
		end--
	}
	return true
}
//快的 循环
func isPalindrome(head *ListNode) bool {
	vals := []int{}
	for ; head != nil; head = head.Next {
		vals = append(vals, head.Val)
	}
	n := len(vals)
	for i, v := range vals[:n/2] {
		if v != vals[n-1-i] {
			return false
		}
	}
	return true
}

func main() {
	l := &ListNode{1, &ListNode{2, &ListNode{2, nil}}}
	print(isPalindrome(l))
}

